package com.jp.algorithm.graph;

import java.util.*;

public class Alien {

    public static String alienOrder(String[] words) {
        if(words.length==0){
            return "";
        }
        if(words.length==1){
            return ""+words[0].charAt(0);
        }
        //构建图的邻接表
        Map<Character, List<Character>> adjacencyList = new HashMap<>();
        for(int i=0;i<words.length-1;i++){
            String s1 = words[i];
            String s2 = words[i+1];
            int l1 = s1.length();
            int l2 = s2.length();

            for(int j=0;j<Math.max(l1,l2);j++){
                Character c1 = j < l1 ? s1.charAt(j) : null;
                Character c2 = j < l2 ? s2.charAt(j) : null;
                if(c1 != null && !adjacencyList.containsKey(c1)){
                    adjacencyList.put(c1,new ArrayList<>());
                }
                if(c2 != null && !adjacencyList.containsKey(c2)){
                    adjacencyList.put(c2,new ArrayList<Character>());
                }
                if(c1!=null && c2 !=null && c1!=c2){
                    adjacencyList.get(c1).add(c2);
                }
            }
        }

        Set<Character> visited = new HashSet<>();
        Set<Character> loop = new HashSet<>();
        Stack<Character> stack = new Stack<>();
        for(Character key : adjacencyList.keySet()){
            if(!visited.contains(key)){
                if(!topSort(adjacencyList,stack,loop,visited,key)){
                    return "";
                }
            }

        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }
    public  static boolean topSort(Map<Character,List<Character>> adjacencyList, Stack<Character> stack,Set<Character> loop,Set<Character> visited,char c){
        System.out.println(c);
        loop.add(c);
        visited.add(c);
        for(char u : adjacencyList.get(c)){
            if(loop.contains(u)){
                return false;
            }
            if(!visited.contains(u)){
                if(!topSort(adjacencyList,stack,loop,visited,u)){
                    return false;
                }
            }
        }
        loop.remove(c);
        stack.push(c);
        return true;
    }

    public static void main(String[] args) {
        String[] s = new String[5];
        s[0]="wrt";
        s[1]="wrr";
        s[2]="er";
        s[3]="ett";
        s[4]="rftt";

        alienOrder(s);

    }
}
